package a.codetop.笔试框架.其他;


import org.junit.Test;

import java.util.*;

public class 索引单调栈 {

    //————————————————————————模板————————————————————————————————————————————————————————————
    public int[] index单调栈模板(int[] nums){
        int n=nums.length;
        int[] res=new int[n];
        Stack<Integer> s = new Stack<>();
        //
        for(int i=n-1;i>=0;i--){
            while(!s.isEmpty()&&nums[s.peek()]<=nums[i])s.pop();
            //
            res[i]=s.isEmpty()?-1:s.peek();
            //
            s.push(i);
        }
        return res;
    }
    //————————————————————————————————————————————————————————————————————————————————————

    public int[] 下一个更大的数_普通(int[] ned, int[] nums) {
        int n=nums.length;
        //栈"和"res数组存的都是索引，不是val！
        int[] res=new int[n];
        Stack<Integer> s = new Stack<>();
        //
        for(int i=n-1;i>=0;i--){
            while(!s.isEmpty()&&nums[s.peek()]<=nums[i])s.pop();
            res[i]=s.isEmpty()?-1:s.peek();
            //
            s.push(i);//压入当前的索引，不是值
        }
        //
        System.out.println(Arrays.toString(res));
        //
        //再存个原数组唯一val对应的ind的map
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<n;i++)map.put(nums[i],i);
        //
        for(int i=0;i<ned.length;i++){
            int ind=map.get(ned[i]),nextMax=res[ind];
            if(nextMax==-1)ned[i]=-1;
            else ned[i]=nums[nextMax];
        }
        return ned;
    }

    public int[] 下一个更大的数_循环数组(int[] nums) {
        int n=nums.length;
        int[] res=new int[n];
        //
        Stack<Integer> stack = new Stack<>();
        //
        for(int i = 2*n-1; i>=0; i--){
            while(!stack.isEmpty() && stack.peek()<=nums[i%n]) stack.pop();
            res[i%n]=stack.isEmpty()?-1:stack.peek();
            stack.push(nums[i%n]);
        }
        return res;
    }

}
